/*
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 

示例 1：


输入：head = [4,2,1,3]
输出：[1,2,3,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var sortList = function(head) {
    const mergeList = (l, r) => {
        let dHead = new ListNode()
        let p = dHead
        while(l !== null && r !== null){
            if(l.val > r.val){
                p.next = r
                r = r.next
            }else{
                p.next = l
                l = l.next
            }
            p = p.next
        }
        p.next = (l == null ? r : l)
        return dHead.next
    }
    
    const mergeSort = head => {
        if(head == null || head.next == null) return head
        let p = new ListNode()
        p.next = head
        let quick = p;
        let slow = p;
        let r, l;
        while(quick && quick.next){
            quick = quick.next.next
            slow = slow.next
        }
        r = mergeSort(slow.next)
        slow.next = null
        l = mergeSort(head)
        return mergeList(l, r)
    }
    return mergeSort(head)
};